package 树.对称二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Program:IntelliJ IDEA
 * @description:
 * @author:香蕉你个啵娜娜 l.h-p@qq.com
 * @create:2023-01-07 21:44
 **/

public class Solution {
    // 非递归解决
    public boolean isSymmetric(TreeNode root){
        // 队列
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null){
            return true;
        }
        // 左节点和右子节点同时入队
        queue.add(root.left);
        queue.add(root.right);
        // 如果队列不为空就继续循环
        while (!queue.isEmpty()) {
            // 每次两个出队
            TreeNode left = queue.poll(), right = queue.poll();
            // 如果都为空继续循环
            if (left == null && right == null){
                continue;
            }
            // 如果一个为空，一个不为空，说明不是对称的，直接返回false
            if (left == null ^ right== null){
                return false;
            }
            // 如果这两个值不相同，也不是对称的，直接返回false
            if (left.val != right.val) {
                return false;
            }
            // 这里记住入队的顺序，他会每两个两个的出队
            // 左子节点的左子节点和右子节点的右子节点同时入队，因为他俩会同时比较
            // 左子节点的右子节点和右子节点的左子节点同时入队，因为他俩会同时比较
            queue.add(left.left);
            queue.add(right.right);
            queue.add(left.right);
            queue.add(right.left);

        }
        return true;
    }

    // 递归解决
    public boolean itisSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        return isSymmetricHelper(root.left, root.right);
    }

    public boolean isSymmetricHelper(TreeNode left, TreeNode right){
        // 如果左右子节点都为空，说明当前节点是叶子节点，返回true
        if (left == null && right == null){
            return true;
        }
        // 如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        // 然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
        return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
    }

}
